package com.sise.Tree;

/**
 *      111. 二叉树的最小深度
 *      给定一个二叉树，找出其最小深度。
 *      最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *      说明：叶子节点是指没有子节点的节点。
 *
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：2
 *
 *      解题思路：
 *      1、叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
 *      2、当 root 节点左右孩子都为空时，返回 1
 *      3、当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
 *      4、当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值
 *
 */
public class _111_minDepth {

    /**
     *      简洁版
     */
    public int minDepth_2(TreeNode root){
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        // 1、如果左孩子和右孩子有为空的情况，直接返回 left + right + 1 (因为为空的话，那么返回的值是 0，故此加起来结果相同)
        // 2、如果都不为空，返回较小深度 +1
        return root.left == null || root.right == null ? left + right + 1: Math.min(left, right) + 1;
    }

    /**
     *      DFS、递归
     */
    public int minDepth(TreeNode root) {
        // root 为空说明到底了
        if (root == null) return 0;

        // 1、左右子节点为空，那么自身的高度就为 1
        if (root.left == null && root.right == null){
            return 1;
        }

        // 2、能到达这一步，说明左右子节点不会同时为空。①左节点或右节点为空（如果传递参数为空，那么返回 0 即可） ②左右子节点都不为空
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        // 这里延续第二步，必然有一个节点为空，那么返回 left + right + 1。因为 left 或 right 有一个的返回值为 0，故此结果相同
        if (root.left == null || root.right == null){
            return left + right + 1;
        }

        // 3、最后一种情况，左右子节点都不为空，那么返回最小深度 + 1
        return Math.min(left, right) + 1;
    }


    /**
     *      BFS解法 - 见 BFS 的例子
     */



}
